package class_4;

import java.util.Arrays;
import java.util.Random;

public class Coding_Decodeways2 {
	public static long mod = 1000000007;
	/**
	 * 动态规划法
	 * 自底向上法
	 */
	public static int numDecodings1(String str) {
		if(str==null || str.length()<1) {
			return 0;
		}
		char[] s = str.toCharArray();
		int n = s.length;
		long[] dp = new long[n+1];
		dp[n] = 1;
		for(int i = n-1;i>=0;i--) {
			if(s[i]=='0') {
				dp[i] = 0;
				continue;
			}
			//单个字符转化讨论
			dp[i] = dp[i+1] * (s[i]=='*'? 9: 1);
			if(i+1<n) {
				if(s[i]!='*') {
					if(s[i+1]!='*') {
						if(((s[i]-'0') * 10 + (s[i+1] - '0') )<= 26) {
							dp[i] += dp[i+2];
						}
					}
					else {
						//s[i+1]是*, s[i]是数字字符
						switch(s[i]) {
						case '1':
							dp[i] += 9 * dp[i+2];//要么1* ,有9种情况
							break;
						case '2':
							dp[i] += 6 * dp[i+2];// 要么2*, 有6种情况
							break;
						}
					}
				}
				else {
					//s[i] is *
					if(s[i+1]!='*') {
						if(s[i+1]<='6') {
							dp[i] += 2 * dp[i+2];//1->6 , 2->6两种情况
						}
						else {
							dp[i] += dp[i+2];//只有1->*的情况可以对应
						}
					}
					else {
						//s[i+1]是数字字符
						dp[i] += 15 * dp[i+2];//11 ~ 26共有15个字符。 因为两个字符组合从11开始
					}
				}
			}
			dp[i] %= mod;//同余原理
		}
		return (int)dp[0];
	}
	/**
	 * 最优解方法
	 * 严格位置依赖和一维空间压缩
	 * @param str 给定字符串
	 * @return
	 */
	public static int numDecodings2(String str) {
		if(str==null || str.length()<1) {
			return 0;
		}
		char[] s = str.toCharArray();
		int n = s.length;
		long cur = 0, next = 1, nextNext = 0;
		for(int i=n-1;i>=0;i--) {
			cur = 0;//重置cur = 0;
			if(s[i]!='0') {
				cur += next * (s[i]=='*'?9:1);
				if(i+1<n) {
					if(s[i]!='*') {
						if(s[i+1]!='*') {
							if((s[i]-'0') * 10 + s[i+1] - '0' <= 26) {
								cur += nextNext;
							}
						}
						else {
							if(s[i]=='1') {
								cur += 9 * nextNext;
							}
							else if(s[i]=='2') {
								cur += 6 * nextNext;
							}
						}
					}
					else {
						//s[i] is digit character
						if(s[i+1]!='*') {
							if(s[i+1]<='6') {
								cur += 2 * nextNext;
							}
							else {
								cur += nextNext;
							}
						}
						else {
							cur += (9+6)*nextNext;
						}
					}
				}
			}
			nextNext = next;
			next = cur;
		}
		return (int)cur;
	}
	public static int MAX = 100;
	public static char[] ch = new char[MAX];
	public static long random() {
		return (long)(Math.random() * 10);
	}
	public static void main(String[] args) {
		Random random = new Random();
		int n = random.nextInt(MAX);
		int num = 0;
		for(int i=0;i<n;i++) {
			num = random.nextInt(11);
			if(num==10) {
				ch[i] = '*';
			}
			else {
				ch[i] = (char)(num + '0');
			}
		}
		String s = new String(ch,0,n);
	    System.out.println("字符串长度: " + n);
		 // 为了避免打印过长的字符串，截断显示部分内容
        if (n > 50) {
            System.out.println("字符串: " + s.substring(0, 50) + "...");
        } else {
            System.out.println("字符串: " + s);
        }

        // 暴力递归方式计算解码方案
        long start = System.nanoTime();
        int ret = numDecodings1(s);
        long end = System.nanoTime();
        System.out.println("解码方案数 (严格位置依赖): " + ret);
        System.out.println("严格位置依赖动态规划耗时: " + (end - start) + " 纳秒");
//        
//        // 带缓存表的dp方式计算解码方案
//        start = System.nanoTime();
//        ret = numDecodings(s);
//        end = System.nanoTime();
//        System.out.println("解码方案数 (动态规划): " + ret);
//        System.out.println("动态规划（自顶向下）耗时: " + (end - start) + " 纳秒");
	}
}
